import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mac
 * Date: 2022-10-28
 * Time: 17:38
 */
public class Day11 {
    //506，相对名次 - 标记
    public String[] findRelativeRanks(int[] score) {
        int ret[] = Arrays.copyOf(score, score.length);
        Arrays.sort(ret);
        String[] answer = new String[score.length];

        for (int i = 0; i < score.length; i++) {
            for (int j = 0; j < score.length; j++) {
                if (score[i] == ret[j]){
                    if (j + 1 == score.length){
                        answer[i] = "Gold Medal";
                    }else if (j + 1 == score.length - 1){
                        answer[i] = "Silver Medal";
                    }else if (j + 1 == score.length - 2){
                        answer[i] = "Bronze Medal";
                    }else{
                        answer[i] = score.length - j + "";
                    }
                }
            }
        }
        return answer;
    }
    //HashMap解法
    public String[] findRelativeRanks1(int[] score) {
        int len = score.length;
        int ret[] = Arrays.copyOf(score, len);
        Arrays.sort(ret);
        Map<Integer,Integer> map = new HashMap<>();

        for (int i = 0; i < len; i++) {
            map.put(ret[i], len - i);
        }

        String[] answer = new String[len];
        for (int i = 0; i < len; i++) {
            int cnt = map.get(score[i]);
            if (cnt == 1){
                answer[i] = "Gold Medal";
            }else if (cnt == 2){
                answer[i] = "Silver Medal";
            }else if (cnt == 3){
                answer[i] = "Bronze Medal";
            }else{
                answer[i] = cnt + "";
            }
        }
        return answer;
    }
    //561.数组拆分 - 标记 - 理解
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int sum = 0;

        for (int i = 0; i < nums.length; i += 2) {
            sum += nums[i];
        }

        return sum;
    }

    //566.重塑矩阵
    public int[][] matrixReshape(int[][] mat, int r, int c) {
        int[][] array = new int[r][c];
        if (r * c != mat.length * mat[0].length){
            return mat;
        }
        int k = 0, q  =0;
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++) {
                array[k][q] = mat[i][j];
                q++;
                if (q >= c){
                    k++;
                    q = 0;
                }
            }
        }
        return array;
    }
    //575.分糖果
    public int distributeCandies(int[] candyType) {
        Set<Integer> set = new HashSet<>();

        for (int i = 0; i < candyType.length; i++) {
            set.add(candyType[i]);
        }
        int ret = set.size();

        if (ret > candyType.length / 2){
            ret = candyType.length / 2;
        }
        return ret;
    }
    //594.最长和谐子序列 - 标记 - O(n^2)
    public static int findLHS(int[] nums) {
        int count = 0;
        int ret = 0;
        int ret1 = 0;
        int ret2 = 0;
        for (int i = 0; i < nums.length; i++) {
            ret = 0;
            ret1 = 0;
            ret2 = 0;
            if (i > 0 && nums[i] == nums[i - 1]){
                i++;
                continue;
            }
            for (int j = 0; j < nums.length; j++) {
                if (nums[j] == nums[i] + 1){
                    ret1++;
                }
                if (nums[j] == nums[i]){
                    ret2++;
                }
            }
            if (ret1 + ret2 > ret2){
                ret = ret1 + ret2;
            }
            if (ret > count){
                count = ret;
            }
        }
        return count;
    }
    //HashMap解法 - O(n)
    public int findLHS1(int[] nums) {
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        int ret = 0;

        for (int num: nums){
            hashMap.put(num, hashMap.getOrDefault(num, 0) + 1);
        }

        for (int key: hashMap.keySet()){
            if (hashMap.containsKey(key + 1)){
                ret = Math.max(ret, hashMap.get(key) + hashMap.get(key + 1));
            }
        }
        return ret;
    }
    //双指针解法 - 了解
    //598.范围求和
    public int maxCount(int m, int n, int[][] ops) {
        if (ops.length == 0){
            return m * n;
        }
       int ret1 = ops[0][0];
       int ret2 = ops[0][1];
        for (int i = 1; i < ops.length; i++) {
             if (ret1 > ops[i][0]){
                 ret1 = ops[i][0];
             }
             if (ret2 > ops[i][1]){
                 ret2 = ops[i][1];
             }
        }
        return ret1 * ret2;
    }
    public static void main(String[] args) {
        int[] array = {-3,-1,-1,-1,-3,-2};
        int ret = findLHS(array);
        System.out.println(ret);
    }
}
